Communication between devices in a communication system conventionally involves communication sessions, each session involving two devices, or optionally a larger sub-group of all devices. A common example is a session involving a first and second mobile telephone device, started by dialing the telephone number of the first device from the second device. The session may involve exchanging speech signals selectively between the two devices, and/or data signals, such a signals used to control a common game controlled from the two devices.
Various conditions can be imposed by the devices in order to decide whether or not to allow the establishment of a session. A familiar condition is that a receiving mobile telephone device compares the telephone number of the calling mobile telephone device against a list of allowed (or prohibited) numbers and establishes the session only if the caller's telephone number is on the list of allowed numbers (or not if the caller's telephone number is on the list of prohibited numbers).
A disadvantage of such methods of establishing sessions is that confidential information that the caller indeed attempted to establish the call, may needlessly be revealed. If this information must be kept secret, this may be partly achieved by letting pairs of communication devices run through session establishment processes independent of whether establishment of a session is requested. However, at some stage during such a session establishment process the calling device must reveal whether it actually requests to establish a session, thereby possibly enabling the other communication device to obtain information about this before the other communication device has indicated whether the request will be accepted. On the other hand, if the other communication device has to indicate that a request will be accepted before the request has been revealed, information about the list of allowed (or prohibited) numbers may leak out without establishing a communication session.
Concepts from cryptography may be considered to prevent that such information is revealed. A. Montreuil and J. Patarin have published an article titled “The Marriage Proposal Problem: Fair and Efficient Solution for Two-Party computations”, in A. Canteaut and K. Viswanathan (Eds.): INDOCRYPT 2004, LNCS 3348, pp. 33-47, 2004. Herein the “Marriage Proposal Problem” is a colorful name for the problem of letting two parties determine whether they agree to a proposal, without letting the parties know whether the other party agreed if the parties do not both agree. Apart from more technical applications, such a determination could conceivably also be used in amorous relations between professors of mathematics, if they are extremely persistent.
In terms of logic operations, Montreuil et al disclose a method that allows two parties to compute the AND function of two logic (binary) values that are each available to a respective one of the parties only. A four step algorithm is used for solving this problem. The algorithm is designed to provide for two computation routes to compute a “match number” dependent on the logic values. The match numbers obtained via the respective computation routes are equal only if the logic values with predetermined logic values are used. Each computation route to compute the match number involves random information available only to a respective one of the parties and the logic value of that party, as well as information from the other party that depends in a cloaked way on the logic value and random information from the other party.
Montreuil's algorithm is based on the “discrete logarithm assumption”, which says that given a result obtained by raising a known number to a random exponent, it is practically impossible to compute the exponent from that result if sufficiently large numbers are used. The discrete logarithm assumption makes it possible to prove knowledge of a secret (random) exponent while keeping the exponent itself secret, by disclosing results of raising numbers to the secret exponent to allow verification that a common exponent has been used.
In a first step of Montreuil's algorithm both parties mutually commit themselves to fix their own secret random exponent by means of this assumption. In a second step both parties compute functions of their logic values, again raising numbers to exponents, this time using their own logic value in the exponent together with random information that cloaks the logic value. In a third step both parties compute products that combine their mutual results from the second step and raise products to the secret random exponent to which they committed themselves in the first step. The third step results in match numbers that have been computed along different routes, and for which it can respectively be verified that each can be computed only if the secret random exponent has been used to which the respective parties have committed themselves in the first step. Finally, the match numbers are compared. Montreuil et al have proved that their algorithm is robust against various attacks to discover the secret logic values by devices that do not reveal their own logic value to the other.
Applied to the establishment process of a communication session between communication devices such as mobile telephones, this algorithm would involve the selection of random numbers in the mobile telephones, computation of exponentiations using various exponents, transmitting computed numbers to the other mobile telephone, performing further computations etc. Finally, the mobile phones establish a joint communication session only if resulting match numbers are equal. When the match numbers are not equal, the algorithm ensures that the mobile telephone that was the cause of the mismatch has no information whether the other mobile telephone was not also the cause of the mismatch.
However, although such a process is robust against attacks in a one-to-one process, it is less robust in a more open environment, where further conditions may be imposed. For example, in a system with many devices, wherein it is intended that each device is enabled only to establish sessions with a secret few preselected eligible devices, the process may not be robust against an attacker device that attempts a search for other devices for which it is eligible without letting the other devices detect this, or a “desperate” attacker device that attempts to establish a communication session with any device that has made the attacker eligible.